class MedianFinder {//leetcode395——数据流中的中位数
public:
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(n==0) {
            l_heap.push(num);
            n++;
        }
        else if(n==m){
            if(num<=r_heap.top()) l_heap.push(num);
            else if(num>r_heap.top()){
                l_heap.push(r_heap.top());
                r_heap.pop();
                r_heap.push(num);
            }
            n++;
        }
        else if(n==m+1){
            if(num>=l_heap.top()) r_heap.push(num);
            else if(num<l_heap.top()){
                r_heap.push(l_heap.top());
                l_heap.pop();
                l_heap.push(num);
            }
            m++;
        }
    }
    
    double findMedian() {
        if(n==m){
            return (l_heap.top()+r_heap.top())/2;
        }
        else if(n==m+1){
            return l_heap.top();
        }
        else{
            cout<<"error"<<endl;
        }
        return 0.0;
    }
private:
    priority_queue<double> l_heap;//大堆
    priority_queue<double,vector<double>,greater<double>> r_heap;//小堆
    int n=0;
    int m=0; 
};
